In the field of network science, real-world complex systems are abstracted as complex networks, in which nodes represent individuals and links denote the connections or interactions between individuals.^[1–3] Nowadays, although we can obtain abundant data of various complex systems due to advanced technologies, it is demonstrated that large parts of the data of the complex systems are still not available, and there are non-ignorable errors in the data that we obtain.^[4,5] Thus, new methods are needed to process, correct, and make predictions from the data. Link prediction methods aim to predict the missing or future links among network data.^[6,7] Specifically, they estimate the existence likelihood of links between two nodes based on observed links and nodes’ attributes. Link prediction has broad applications,^[8] such as detecting potential interactions in protein–protein interaction network,^[9] recommending friends and goods in online social networks,^[10] exploring potential coauthor relationships in collaboration networks,^[11] and so on.

Previous algorithms are basically from the field of machine learning, including supervised learning,^[12] Markov chain,^[13] and likelihood estimation.^[14] These algorithms heavily depend on the attributes of nodes, and do not seriously consider the structural characteristics of networks. Besides, their computation cost is inhibitive for large real-world networks.^[15] Recently, the booming network science community has achieved deeper insights into the structure of complex networks,^[1] and further stimulates the research of link prediction.^[6,16] Lots of prediction algorithms based on structural similarity are proposed, which can be classified into three types: local indices,^[17–22] quasi-local indices,^[23,24] and global indices.^[25,26] For example, common neighbors (CN),^[18] preferential attachment (PA),^[17] Adamic–Adar (AA),^[21] and resource allocation (RA)^[22] are local indices, which only use the nearest neighborhood information. Katz,^[25] Leicht–Holme–Newman (LHN),^[26] and SimRank,^[27] which need the knowledge of the whole network topology, are global ones. Quasi-local indices, including local path (LP),^[23] local random walk (LRW),^[24] and superposed random walk (SRW),^[24] need more topological information than local indices, but less topological information than global ones. Generally, local indices have the lowest prediction accuracy, but their computational cost is the smallest among the three types of similarity indices. Global indices are the opposite of local indices, while quasi-local ones are the trade-off between them.

Recently, information entropy has been employed to measure the complexity of the topological structures of complex networks.^[28] Results showed that information entropy can better capture the topological difference than the other typical network measurements.^[29,30] Moreover, information entropy has a natural connection with link prediction problems, in which the probability of a missing link between two nodes can be transformed into the corresponding information entropy. Thus, researchers began to apply information entropy theory to link prediction problems in complex networks.^[31–33] For example, Tan et al.^[31] reexamined the role of common neighbors in link prediction by using the mutual information, and proposed a mutual information-based similarity index. Xu et al.^[32] derived the information entropy of a path, and studied the contributions of paths in link prediction based on path entropy, and finally provided a path entropy based similarity index. Simulation results^[31–33] showed that the similarity indices based on information entropy have higher prediction accuracy than the other types of similarity indices.

In real society, the interactions between individuals are of different strengths for many complex networks, which are called weighted networks.^[2,34] For instance, in the air traffic network, the weight of a link is measured by the number of passengers in the related flight. In the router-level of the Internet, the weights of links are generally correlated with the bandwidth of the physical connections or the cost for data transmission between routers. In social networks, weights of links are related to the interacting times or frequencies between individuals. Therefore, it is reasonable to consider the link weights when designing link prediction algorithms to further improve the prediction accuracy. So far there have been a few tries in the literature. Murata and Moriyasu^[35] improved the CN and AA indices by using the link weights information. Bai et al.^[36] developed the weighted version of the LP index. Lü et al.^[37] particularly explored the role of weak ties in link prediction and found that weak ties can improve the prediction accuracy effectively. Simulation results showed that the weighted version of these typical similarity indices indeed have a higher accuracy than the original ones. However, they still have a large space to improve. For example, the weighted and unweighted versions of AA and CN indices only utilize the information of paths with length 2, which can be further improved by considering longer paths, such as paths with length 3. In addition, although the LP index considers paths of length 3, it only cares about the number of paths for unweighted networks or the sum of link weights for weighted networks, while the topological information of those paths can be further explored to improve the prediction accuracy.

In this paper, we apply information entropy to link prediction in weighted networks. Specifically, we reexamine the role of paths in link prediction by considering both the path entropy and the path weight, and propose a weighted similarity index applicable to the weighted networks. Through simulation on real-world weighted networks, we show the prediction accuracy of our index and make comparisons with other typical weighted indices.

Quantitative measurement of complex networks is a hot topic in network science,^[1] and various measurements are proposed, including degree, betweenness, closeness, k-core number, and so on.^[2] However, most of the measurements are for nodes and links, and only a very few are particularly for paths, such as path length^[38] and path attack centrality.^[39] In our latest work,^[32] we applied information theory to measure the importance of paths, and specifically we derived the entropy of a path. Assuming that L _ab ¹ (L _ab ⁰) represents the event that there is (not) a link between nodes a and b in the network without degree correlation. Then, the probability of L _ab ¹ is calculated by

(1)

(2)

For a simple path of length δ, the occurrence possibility can be calculated approximately by

(3)

(4)

Although the weights of links and weighted networks have been well discussed, there is no specific result about the weights of paths. In traffic routing protocols, we usually choose the optimal path, of which the sum of the cost of all links is the smallest among the candidate paths.^[40–42] Enlightened by this, here we define the weight of path D as the sum of its links’ weights,

(5)

In the framework of information theory, the probability of link existence between two nodes can be expressed with information entropy. Then, the link prediction problem can be defined as the conditional entropy,^[31] that is

(6)

Previous results showed that the longer the path is, the less important the path is in link prediction. Moreover, results demonstrated that the link weights can be used to improve the prediction accuracy. Here we combine the path length, path weight, and path entropy to calculate the contribution of path D with length i in the link prediction:

(7)

(8)

(9)

Assuming an undirected network , where V, E, and W denote the sets of nodes, links, and link weights, respectively. In W, , which means there is no direction for the weight between two nodes. To measure the predicting ability of an index, E is usually randomly divided into two parts: a training set (in this paper, 90% of all links) and a probe set (10% of all links). Clearly, and .

Two standard metrics, AUC and precision, are applied to quantify the prediction quality. To calculate AUC, n times of independent score comparisons are made between node pairs in and U − E. Each time we select a node pair randomly from these two sets respectively and compare their scores. If there are times that the score of the link from is higher (or smaller in the case of WPE) than the link from U − E, and times that they have the same scores, AUC is calculated as

(10)

(11)

Next, we introduce three indices and their weighted versions that we use for comparison. They are common neighbors (CN),^[18] Adamic–Adar index (AA),^[21] and local path (LP),^[23] which are defined as

(12)

(13)

(14)

(15)

(16)

(17)

Six weighted networks from disparate fields are used to test the accuracy for various prediction indices. The directions of links are ignored. The self-connections and multiple links are deleted from the network data. For the unconnected networks, we select the maximum connected components for experiments. The statistics of these networks are summarized in Table 1. i) Les.^[43] This undirected network contains co-appearances of characters in Victor Hugo’s novel ‘Les Misérables’. A node represents a character and a link between two nodes shows that these two characters appeared in the same chapter of the book. The weight of each link indicates how often such a co-appearance occurred. ii) USAir.^[44] This is the network of US air transportation, where nodes represent airports, links represent routes between airports, and the weight of a link is the frequency of flights between two airports. iii) Bomb.^[45] This undirected network contains contacts between suspected terrorists involved in the train bombing of Madrid on March 11, 2004 as reconstructed from newspapers. A node represents a terrorist and a link between two terrorists shows that there was contact between the two terrorists. The link weights denote how strong a connection was, by considering the friendship and co-participation in training camps or previous attacks. iv) Bible.^[46] This undirected network contains nouns (places and names) of the King James version of the Bible and information about their co-occurrences. A node represents one of the above noun types and a link indicates that two nouns appeared together in the same Bible verse. The link weights show how often two nouns occurred together. v) Florida.^[47] This network contains the carbon exchanges in the cypress wetlands of South Florida during the dry season. Nodes represent taxa and a link denotes that a taxon uses another taxon as food with a given trophic factor, which is the basis of link weight. vi) C. elegans.^[48] This is the neural network of the nematode worm C. elegans, where a node represents a neuron, a link joins two nodes if the corresponding neurons have synaptic contacts, and the weight represents the number of synapses between two neurons.

Table 1.

Table 1.

Table 1. The topological statistics of six real-world weighted networks. is the number of nodes. represents the number of links. is the average degree. H represents the degree heterogeneity, defined as . C is the clustering coefficient. . Networks H C Les 77 278 7.2338 1.9654 0.4634 USAir 332 2126 12.8072 3.4639 0.7494 Bomb 70 256 7.3429 2.3645 0.7122 Bible 1773 9131 10.3001 4.0115 0.7208 Florida 128 2106 32.9063 1.2307 0.3346 C. elegans 297 2148 14.4646 1.8008 0.3079

Table 1. The topological statistics of six real-world weighted networks. is the number of nodes. represents the number of links. is the average degree. H represents the degree heterogeneity, defined as . C is the clustering coefficient. .

To investigate the ability of our prediction index, we perform experiments on the six weighted networks, and make comparisons with three other typical indices. Both the unweighted and weighted versions of these indices are tested. The link weights of the networks are only considered when calculating the weighted versions of these indices. In addition, for the weighted versions of these indices, we adjust the control parameter α to achieve the near optimal performances measured by AUC and precision. For the PE and WPE indices, l = 2 means only paths with length of 2 are used in the calculation, while l = 3 indicates that paths with lengths of both 2 and 3 are used in the calculation. In theory, we can use the information of all paths in link prediction, but in real experiments, we usually consider only short paths, since short paths are more important than long paths in link prediction. On the other side, the longer the paths are, the larger the computational cost is. Our simulation results are shown in Tables 2 and 3, as well as Figs. 1 and 2. Each value is the average of 100 independent runs. In the tables, the maximum performances for each network are marked in bold font.

Fig. 1.

	Figure Option ViewDownloadNew Window
	Fig. 1. AUC versus α for the weighted indices: (a) Les, (b) USAir, (c) Bomb, (d) Bible, (e) Florida, (f) C. elegans.

Table 2.

Table 2.

Table 2. Prediction accuracy measured by AUC for the unweighted and weighted indices. For the weighted indices, we present the maximum AUC with the corresponding control parameter in the brackets. . Nets index WAA AA WLP LP WCN CN WPE(l = 2) PE(l = 2) WPE(l = 3) PE(l = 3) Les 0.967477(0.6) 0.962911 0.96254(0.3) 0.955112 0.963042(0.3) 0.955129 0.97055(0.6) 0.964639 0.956291(0.4) 0.953417 USAir 0.967732(−0.5) 0.965757 0.954597(−0.3) 0.951873 0.963738(−0.7) 0.953757 0.971917(−0.2) 0.969813 0.966167(−1) 0.946596 Bomb 0.944603(0.7) 0.944998 0.938329(0.2) 0.937651 0.934543(0.5) 0.934408 0.957373(1.2) 0.954435 0.940593(−0.5) 0.939566 Bible 0.985164(0.2) 0.985157 0.978042(−0.8) 0.975619 0.977955(−0.1) 0.976989 0.988501(0.2) 0.987872 0.964088(−0.9) 0.95649 Florida 0.611155(0.1) 0.606072 0.783328(−0.3) 0.668619 0.609324(0.1) 0.604758 0.59479(1.4) 0.562404 0.863607(0.1) 0.860174 C. elegans 0.868117(0.1) 0.866639 0.868887(0) 0.868344 0.850465(−0.1) 0.850071 0.87321(0.2) 0.871474 0.885356(0) 0.885356

Table 2. Prediction accuracy measured by AUC for the unweighted and weighted indices. For the weighted indices, we present the maximum AUC with the corresponding control parameter in the brackets. .

Tables 2 and 3 show that it is generally necessary to consider the link weights since the weighted version of these indices achieves higher prediction accuracy than the unweighted ones when the appropriate control parameter is considered (the near optimal parameters are given in the tables). Furthermore, Table 2 indicates that from the perspective of AUC, the prediction accuracy of all the unweighted indices is already high for all the six real-world networks, so that the improvements of the weighted versions are not significant. However, as shown in Table 3, the improvements of the weighted versions are more obvious from the perspective of precision. Moreover, we can see that for all the unweighted and weighted prediction indices, WPE always has the best performances for all the six real-world networks. Especially, for the networks of Bible, Florida, C. elegans, and USAir, we can see from Table 3 that PE and WPE are much better than the other prediction indices. It is worth mentioning that for PE and WPE, extra consideration of the contributions of longer paths is not always necessary and sometimes adverse for link prediction. For instance, we can see that for some networks l = 2 is better than l = 3.

Table 3.

Table 3.

Table 3. Prediction accuracy measured by precision (top-100) for the unweighted and weighted indices. . Nets⧹index WAA AA WLP LP WCN CN WPE(l = 2) PE(l = 2) WPE(l = 3) PE(l = 3) Les 0.2212(0.2) 0.2192 0.2077(0.3) 0.2043 0.2162(0.3) 0.2112 0.2227(0.5) 0.2205 0.21(0.2) 0.2076 USAir 0.6514(−0.3) 0.6324 0.6207(−0.4) 0.6094 0.633(−0.3) 0.6115 0.5926(0.1) 0.5854 0.6704(−0.1) 0.6672 Bomb 0.2026(0) 0.1988 0.1749(−1) 0.1678 0.1886(0.5) 0.188 0.2157(1.6) 0.2101 0.1861(−0.9) 0.1814 Bible 0.5853(−1.5) 0.5602 0.3839(−0.4) 0.3798 0.4375(−0.1) 0.4371 0.8536(−0.1) 0.8508 0.3859(0.4) 0.3812 Florida 0.144(0.3) 0.0912 0.2797(−0.2) 0.1314 0.1384(0.2) 0.0965 0.0614(0.1) 0.0228 0.4826(0) 0.4826 C. elegans 0.1895(1.4) 0.1328 0.1757(0.6) 0.1371 0.1824(1.5) 0.1384 0.1293(0.2) 0.1262 0.2044(0.3) 0.1841

Table 3. Prediction accuracy measured by precision (top-100) for the unweighted and weighted indices. .

Figure 1 and 2 show how the weight affects the prediction accuracy for the weighted indices. For WPE, we focus on path weight defined as the sum of all the link weights in the path, while the other weighted indices only consider link weights. We can see that for WPE, generally both AUC and precision increase first, and then decrease with the control parameter α, and there are optimal parameters (given in Tables 2 and 3) corresponding to the maximum performances. The curves of the other weighted indices have the similar change trends. These results indicate that the prediction accuracy is sensitive to path weights for WPE and link weights for the others, and we should balance the influences of the weak ties and strong ties by appropriately choosing the control parameter to achieve high prediction accuracy. Moreover, we should be slightly biased to the contributions of weak ties, since the simulations results demonstrate that the optimal parameters are less than 1 for all the six networks except Bomb (for WAA and WCN, C. elegans is also an exception).

Fig. 2.

	Figure Option ViewDownloadNew Window
	Fig. 2. Precision (top-100) versus α for the weighted indices: (a) Les, (b) USAir, (c) Bomb, (d) Bible, (e) Florida, (f) C. elegans.

In summary, we study the link prediction problem in weighted complex networks from the perspective of information entropy. In fact, the likelihood of a link between two nodes can be converted into entropy, and small entropy corresponds to large probability of link existence. In this paper we consider the contributions of simple paths between node pairs in link prediction. Specifically, we measure the contribution of an existing path by considering its length, entropy, and weight which is further defined as the sum of link weights in the path. Furthermore, we propose a weighted path entropy (WPE) index for link prediction by considering the contributions of all existing simple paths. Through simulation on several real-world weighted networks, we find that WPE has higher prediction ability measured by AUC and precision than the other typical weighted similarity indices. In fact, the PE index proposed in our previous work already has high prediction accuracy. Thus, by appropriately considering the path weight, WPE further improves the prediction accuracy. We also find that a weak tie is more critical than a strong tie in link prediction. Note that in our context, a weak tie refers to a path with small weight, while in the other works a weak tie means a small weight link.